package com.fang.sort;

import java.util.Comparator;

import com.fang.base.utils.SwapUtils;

public class InsertSort {

	public static void main(String[] args) {
		Integer[] sort = { 2, 5, 45, 87, 1, 254, 58 };

		InsertSort insertSort = new InsertSort();
		Integer[] data = insertSort.sort(sort, new Comparator<Integer>() {

			@Override
			public int compare(Integer data1, Integer data2) {
				if (data1 < data2)
					return 1;
				if (data1 > data2)
					return -1;
				return 0;
			}
		});
		for (Integer integer : data) {
			System.out.print(integer + "   ");
		}
	}

	/**
	 * 具体算法描述如下：
	 * 
	 * 1.从第一个元素开始，该元素可以认为已经被排序 2.取出下一个元素，在已经排序的元素序列中从后向前扫描
	 * 3.如果该元素（已排序）大于新元素，将该元素移到下一位置 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
	 * 5.将新元素插入到下一位置中 6.重复步骤2~5
	 * 
	 * @param data
	 * @param comparator
	 * @return
	 */

	public <T> T[] sort(T[] data, Comparator<? super T> comparator) {
		if (data == null || comparator == null)
			return data;

		for (int i = 1; i < data.length; i++) {
			for (int j = i; j > 0; j--) {
				if (comparator.compare(data[j], data[j - 1]) > 0) {
					SwapUtils.swap(data, j, j - 1);
				} else {
					// 此时插入的数据已经到达正确位置
					break;
				}
			}
		}

		return data;
	}
}
